An ad hoc wireless network is constructed from independent wireless transceivers communicating between each other without benefit of other infrastructure. Thus, ad hoc wireless networks are unlike wired or even cellular networks that require a physical infrastructure. Wired environments require the placing of cables. Cellular networks require the availability of base stations to support communications. For example, an ad hoc wireless network environment may comprise a group of transceivers carried by people randomly dispersed over a geographic area. Each transceiver has a limited range of transmission and reception. A “neighbor” or “neighboring” transceiver is defined herein as one within the transmission range of a given transceiver, i.e., neighbors are able to directly communicate. Networks must be created to allow the networked transceivers to communicate between non-neighboring transceivers through intermediate neighboring transceivers.
In ad hoc environments such as emergency relief or battlefield deployments, the reliance on either wired or cellular networks is often not desired or possible. Thus, although the lack of a required physical infrastructure makes ad hoc networks seem appealing, this lack of physical infrastructure imposes several difficulties. Since there is no physical infrastructure, each communicating device, or transceiver, must support all of its physical needs, e.g., power, as well as its logical needs, e.g., a message routing backbone. Setting up this backbone is a must to guarantee efficient networked communication among the communicating parties. Since all resources are at a premium, the goal of any constructed ad hoc network must be that the network is efficient, i.e., communication between two particular transceivers involves as few nodes, i.e., transceivers, as possible. Further, creation of the ad hoc network backbone by message traffic among the transceivers must be done efficiently, i.e., with a minimum amount of message traffic to establish the ad hoc network backbone. Further, message length itself is desirably kept to a minimum.
Prior attempts have not established optimal efficiency with regard to the creation and operation of an ad hoc wireless network. Prior approaches generally require each transceiver to have “two-hop neighborhood” information, i.e., each transceiver must obtain, retain, and communicate information regarding a neighbor and the next level transceiver adjacent to that neighbor. Thus a far higher number of messages, each of which are lengthier in size, is required to set up and to operate the network. Also, prior approaches have required a larger than theoretically order optimal backbone network without providing any additional benefit, and thereby introduced additional resource burdens on each transceiver.